/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        56.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/12 12:53
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
// 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
// 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
#include "../header.h"
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        if (n == 0)
            return {};
        vector<vector<int>> merged;
        sort(intervals.begin(),intervals.end());
        merged.emplace_back(intervals[0]);
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] > merged.back()[1]){
                merged.emplace_back(intervals[i]);
            } else
                merged.back()[1] = max(merged.back()[1],intervals[i][1]);
        }
        return merged;
    }
};

